/* vim: set sw=8 ts=8 sts=8 expandtab: */
#include "Cmaid.h"
#include "cmaid_private.h"

/**
 * @defgroup Cmaid_Vector The Vector Implementation
 * @ingroup Implementations
 * @brief The vector implementation
 *
 * The vector is based on a traditional C array  providing a
 * @ref Cmaid_List "list class". Append is in average a O(1), whereas
 * insertion, prepend and remove are O(n) operations. The advantage of the
 * vector over the @ref Cmaid_Link_List "linked list" is that it is using
 * less memory per node. In case of inlined values, i.e. if Cmaid_Value::size
 * is larger then zero, it does not use any extra memory at all. If
 * Cmaid_Value::size is zero, only the pointer address is stored. The case
 * of variable length data (Cmaid_Value::size < 0) is not supported.
 */
#define CMAID_VECTOR_ELEMENT_START_COUNT 2

typedef struct Cmaid_Vector Cmaid_Vector;

#define CMAID_VECTOR(l) ((Cmaid_Vector *)(l))
#define CMAID_VECTOR_AT(l, i) ((l)->value->size != 0 ? \
                (void *)((l)->array + ((l)->value->size * (i))) : \
                ((void **)(l)->array)[i])

struct Cmaid_Vector
{
        Cmaid_Container container;
        unsigned char *array;
        size_t array_size;
        Cmaid_Iter *iter_list;
        const Cmaid_Value *value;
};

/*
 * Declaration of the internal used functions
 */
/* container functions */
static void  cmaid_vector_clear(Cmaid_Container *c);
static void  cmaid_vector_iter_attach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_vector_iter_detach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_vector_destroy(Cmaid_Container *c);
static int   cmaid_vector_dump(Cmaid_Container *c, FILE *file);
/* list functions */
static void *cmaid_vector_append(Cmaid_List *t, const void *data);
static void *cmaid_vector_prepend(Cmaid_List *t, const void *data);
static void  cmaid_vector_first_remove(Cmaid_List *t);
static void  cmaid_vector_last_remove(Cmaid_List *t);
static void *cmaid_vector_first(Cmaid_List *t);
static void *cmaid_vector_last(Cmaid_List *t);
static void *cmaid_vector_insert_before(Cmaid_List *t, const Cmaid_Iter *it,
                const void *data);
static void *cmaid_vector_insert_after(Cmaid_List *t, const Cmaid_Iter *it,
                const void *data);
static void  cmaid_vector_sort_with(Cmaid_List *t, Cmaid_Value_Compare_Cb cmp);
static void  cmaid_vector_reverse(Cmaid_List *t);
/* iterator functions */
static void  cmaid_vector_iter_start(Cmaid_Iter *it);
static void *cmaid_vector_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_vector_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_vector_iter_goto(Cmaid_Iter *it, const void *data);
static inline void *cmaid_vector_iter_current(Cmaid_Iter *it);
static void *cmaid_vector_iter_next(Cmaid_Iter *it);
static void *cmaid_vector_iter_previous(Cmaid_Iter *it);
static void  cmaid_vector_iter_remove(Cmaid_Iter *it);
/* array helper functions */
static void *cmaid_vector_insert(Cmaid_Vector *v, int index, const void *data);
static void  cmaid_vector_remove(Cmaid_Vector *v, int index);
static void  cmaid_vector_swap(void *data1, void *data2, size_t size);
static void  cmaid_vector_pointer_array_sort(void **array, int count,
                Cmaid_Value_Compare_Cb cmp);

/*
 * The Interfaces
 */
const Cmaid_List_Interface cmaid_vector_list_if =
{
        {
                CMAID_MAGIC_LIST,
                cmaid_vector_clear,
                cmaid_vector_iter_attach,
                cmaid_vector_iter_detach,
                cmaid_vector_destroy,
                cmaid_vector_dump,
                NULL
        },
        cmaid_vector_append,
        cmaid_vector_prepend,
        cmaid_vector_first_remove,
        cmaid_vector_last_remove,
        cmaid_vector_first,
        cmaid_vector_last,
        cmaid_vector_insert_before,
        cmaid_vector_insert_after,
        cmaid_vector_sort_with,
        cmaid_vector_reverse
};

const Cmaid_Iter_Interface cmaid_vector_iter_if =
{
        cmaid_vector_iter_start,
        cmaid_vector_iter_iter_goto,
        cmaid_vector_iter_index_goto,
        cmaid_vector_iter_goto,
        cmaid_vector_iter_current,
        cmaid_vector_iter_next,
        cmaid_vector_iter_previous,
        cmaid_vector_iter_remove
};

/*
 * inlined helper functions
 */
static inline size_t
cmaid_vector_element_size_get(Cmaid_Vector *v)
{
        /* Note: v->value->size cannot be negative */
        return v->value->size ? (size_t)v->value->size : sizeof(void *);
}

/*
 * Public Functions
 */
/**
 * @param v The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used in the list
 * @return Returns a newly allocated @ref Cmaid_List "list", if an allocation 
 *        error occurs, @c NULL is returned
 * @brief Creates a new list using the hash implementation
 *
 * This functions is creating a @ref Cmaid_List "list" with the vector
 * as implementation.
 *
 * @note Variable length data is not support, hence the size given by @p v
 *       must not be negative.
 */
Cmaid_List *
cmaid_vector_list_new(const Cmaid_Value *v)
{
        Cmaid_Vector *l;
        size_t elm_size;

        if (!v)
                v = &cmaid_value_pointer;
        else if (v->size < 0)
                return NULL;

        l = CALLOC(1, sizeof(Cmaid_Vector));
        if (!l)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(l, &cmaid_vector_list_if);
        if (v)
                l->value = v;
        else
                l->value = &cmaid_value_pointer;

        elm_size = cmaid_vector_element_size_get(l);
        l->array = MALLOC(elm_size * CMAID_VECTOR_ELEMENT_START_COUNT);
        l->array_size = CMAID_VECTOR_ELEMENT_START_COUNT;

        return (Cmaid_List *) l;
}

/*
 * The container functions implementation
 */
static void
cmaid_vector_clear(Cmaid_Container *c)
{
        Cmaid_Vector *l = CMAID_VECTOR(c);
        Cmaid_Iter *it;

        /* free the elements, first the inlined case */
        if (l->value->size && l->value->sized.free)
        {
                int elem_size;
                unsigned char *cur, *end;
                Cmaid_Value_Free_Cb free_cb;

                elem_size = l->value->size;
                cur = l->array;
                end = cur + elem_size * c->count;
                free_cb = l->value->sized.free;

                while (cur != end)
                {
                        free_cb(cur);
                        cur += elem_size;
                }
        }
        /* second the pointer case */
        if (!l->value->size && l->value->pointer.free)
        {
                void **cur, **end;
                Cmaid_Value_Free_Cb free_cb;

                cur = (void **)l->array;
                end = cur + c->count;
                free_cb = l->value->pointer.free;

                while (cur != end)
                {
                        free_cb(*cur);
                        cur++;
                }
        }

        l->array = REALLOC(l->array, CMAID_VECTOR_ELEMENT_START_COUNT
                        * cmaid_vector_element_size_get(l));
        l->array_size = CMAID_VECTOR_ELEMENT_START_COUNT;

        /* and set the iter to the end */
        for (it = l->iter_list; it; it = it->next)
                it->index = -1;

        c->count = 0;
}

static void
cmaid_vector_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        /* XXX we probably need to check if the iter isn't already in the 
         * list */
        it->interface = &cmaid_vector_iter_if;
        it->container = c;
        it->current = NULL;
        it->index = -1;

        /* insert into the iter list */
        it->next = CMAID_VECTOR(c)->iter_list;
        CMAID_VECTOR(c)->iter_list = it;
}

static void
cmaid_vector_iter_detach(Cmaid_Container *c, Cmaid_Iter *it)
{
        Cmaid_Iter **iter_list = &CMAID_VECTOR(c)->iter_list;
        
        cmaid_iterlist_remove(iter_list, it);
}

static void
cmaid_vector_destroy(Cmaid_Container *c)
{
        cmaid_vector_clear(c);
        FREE(CMAID_VECTOR(c)->array);
        FREE(c);
}

static int 
cmaid_vector_dump(Cmaid_Container *c, FILE *file)
{
        Cmaid_Vector *vec = CMAID_VECTOR(c);
        Cmaid_Value_Stringify_Cb cb;
        char buffer[1024];
        unsigned int i;

        cb = vec->value->stringify ? vec->value->stringify :
                cmaid_value_pointer_stringify;

        fprintf(file, "digraph vector%p {\n", c);
        fprintf(file, "\tgraph [rankdir = \"LR\"];\n");

        /* first print the buckets */
        fprintf(file, "\tarray [\n\t\tlabel=\"");
        for (i = 0; i < c->count; i++)
        {
                cb(CMAID_VECTOR_AT(vec, i), buffer, sizeof(buffer));
                if (i == 0)
                        fprintf(file, "%s", buffer);
                else
                        fprintf(file, "| %s", buffer);
        }
        fprintf(file, "\"\n\t\tshape=\"record\"\n\t]\n");
        fprintf(file, "}\n");

        return TRUE;
}

/*
 * The list functions implementation
 */
static void *
cmaid_vector_prepend(Cmaid_List *t, const void *data)
{
        return cmaid_vector_insert(CMAID_VECTOR(t), 0, data);
}

static void *
cmaid_vector_append(Cmaid_List *t, const void *data)
{
        return cmaid_vector_insert(CMAID_VECTOR(t), t->count, data);
}

static void
cmaid_vector_first_remove(Cmaid_List *t)
{
        if (cmaid_container_empty_is(t))
                return;

        cmaid_vector_remove(CMAID_VECTOR(t), 0);
}

static void
cmaid_vector_last_remove(Cmaid_List *t)
{
        if (cmaid_container_empty_is(t))
                return;

        cmaid_vector_remove(CMAID_VECTOR(t), t->count - 1);
}

static void *
cmaid_vector_first(Cmaid_List *l)
{
        Cmaid_Vector *v = CMAID_VECTOR(l);

        if (cmaid_container_empty_is(l))
                return NULL;
        
        return CMAID_VECTOR_AT(v, 0);
}

static void *
cmaid_vector_last(Cmaid_List *t)
{
        Cmaid_Vector *v = CMAID_VECTOR(t);
        
        if (cmaid_container_empty_is(t))
                return NULL;
        
        return CMAID_VECTOR_AT(v, t->count - 1);
}

static void *
cmaid_vector_insert_before(Cmaid_List *t, const Cmaid_Iter *it,
                                const void *data)
{
        Cmaid_Vector *l = CMAID_VECTOR(t);
        
        if (it->index < 0)
                return cmaid_vector_append(t, data);

        return cmaid_vector_insert(l, it->index, data);
}

static void *
cmaid_vector_insert_after(Cmaid_List *t, const Cmaid_Iter *it, const void *data)
{
        Cmaid_Vector *l = CMAID_VECTOR(t);
       
        return cmaid_vector_insert(l, it->index + 1, data);
}

static void
cmaid_vector_sort_with(Cmaid_List *t, Cmaid_Value_Compare_Cb cmp)
{
        Cmaid_Vector *l = CMAID_VECTOR(t);

        if (!cmp)
                cmp = l->value->cmp ? l->value->cmp :
                        cmaid_value_pointer_compare;
        /* if it is an inlined value we can sort it with qsort() */
        if (l->value->size)
                qsort(l->array, t->count, l->value->size, cmp);
        else
                cmaid_vector_pointer_array_sort((void **)l->array, t->count,
                                cmp);
}

static void
cmaid_vector_reverse(Cmaid_List *t)
{
        Cmaid_Vector *v = CMAID_VECTOR(t);
        size_t elem_size = cmaid_vector_element_size_get(v);
        unsigned char *start, *end;

        start = v->array;
        end = v->array + elem_size * (t->count - 1);
        while (start < end)
        {
                cmaid_vector_swap(start, end, elem_size);
                start += elem_size;
                end -= elem_size;
        }
}

/*
 * The iterator functions implementation
 */
static void
cmaid_vector_iter_start(Cmaid_Iter *it)
{
        it->index = -1;
}

static void *
cmaid_vector_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        return cmaid_vector_iter_current(it);
}

static void *
cmaid_vector_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_List *l = it->container;

        if (l->count == 0 || index >= l->count || index < 0)
        {
                cmaid_vector_iter_start(it);
                return NULL;
        }

        it->index = index;
        return cmaid_vector_iter_current(it);
}

static void *
cmaid_vector_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_vector_iter_start(it);
        while ((found = cmaid_vector_iter_next(it)) && found != data)
                ;

        return found;
}

inline static void *
cmaid_vector_iter_current(Cmaid_Iter *it)
{
        if (it->index < 0)
                return NULL;

        return CMAID_VECTOR_AT(CMAID_VECTOR(it->container), it->index);
}

static void *
cmaid_vector_iter_next(Cmaid_Iter *it)
{
        it->index++;
        if (it->index >= cmaid_container_count(it->container))
                it->index = -1;

        return cmaid_vector_iter_current(it);
}

static void *
cmaid_vector_iter_previous(Cmaid_Iter *it)
{
        if (it->index < 0)
                it->index = cmaid_container_count(it->container) - 1;
        else
                it->index--;

        return cmaid_vector_iter_current(it);
}

static void
cmaid_vector_iter_remove(Cmaid_Iter *it)
{
        if (!cmaid_container_empty_is(it->container))
                cmaid_vector_remove(it->container, it->index);
}

/* array helper functions */
static void *
cmaid_vector_insert(Cmaid_Vector *v, int index, const void *data)
{
        Cmaid_Iter *it;
        size_t elem_size = cmaid_vector_element_size_get(v);
        size_t count = ++(CMAID_CONTAINER(v)->count);

        /* first we need to make space for the new element */
        if (v->array_size < count)
        {
                unsigned char *new_array;

                v->array_size *= 2;
                new_array = MALLOC(v->array_size * elem_size);
                /* copy the elements before the new element */
                memcpy(new_array, v->array, index * elem_size);
                /* copy the elements after the new element */
                memcpy(new_array + elem_size * (index + 1),
                                v->array + elem_size * index,
                                (count - index - 1) * elem_size);
                /* we don't need the old array anymore */
                FREE(v->array);
                v->array = new_array;
        }
        else
        {
                memmove(v->array + elem_size * (index + 1),
                                v->array + elem_size * index,
                                (count - index - 1) * elem_size);
        }

        /* now we have to initialize the new space of the element */
        if (v->value->size)
        {
                if (v->value->sized.copy)
                        v->value->sized.copy(v->array + elem_size * index,
                                        data, elem_size);
                else
                        memcpy(v->array + elem_size * index, data, elem_size);
        }
        else
        {
                if (v->value->pointer.dup)
                        ((void **)v->array)[index] =
                                v->value->pointer.dup(data);
                else
                        ((void **)v->array)[index] = (void *)data;
        }

        /* update the iterators */
        for (it = v->iter_list; it; it = it->next)
        {
                if (it->index >= index)
                        it->index++;
        }

        return CMAID_VECTOR_AT(v, index);
}

static void
cmaid_vector_remove(Cmaid_Vector *v, int index)
{
        Cmaid_Iter *it;
        size_t elem_size = cmaid_vector_element_size_get(v);

        /* free the element before we remove it */
        if (v->value->size && v->value->sized.free)
                v->value->sized.free(v->array + index * elem_size);
        else if (!v->value->size && v->value->pointer.free)
                v->value->pointer.free(((void **)v->array)[index]);

        memmove(v->array + index * elem_size,
                        v->array + (index + 1) * elem_size,
                        (CMAID_CONTAINER(v)->count - index - 1) * elem_size);

        if ((size_t)CMAID_CONTAINER(v)->count*3 <= v->array_size)
        {
                v->array_size /= 2;
                v->array = REALLOC(v->array, v->array_size * elem_size);
        }
        
        /* update the iterators */
        for (it = v->iter_list; it; it = it->next)
        {
                if (it->index >= index)
                        it->index--;
        }
        CMAID_CONTAINER(v)->count--;
}

static void
cmaid_vector_swap(void *data1, void *data2, size_t size)
{
        unsigned char tmp[size];

        memcpy(tmp, data1, size);
        memcpy(data1, data2, size);
        memcpy(data2, tmp, size);
}

static void
cmaid_vector_pointer_array_sort(void **array, int count,
                Cmaid_Value_Compare_Cb cmp)
{
        int i, j;

        /* XXX, this is an insertion sort, replace this by something performing
         * O(n*log(n))
         */
        for (i = 1; i < count; i++)
        {
                void *tmp = array[i];
                for (j = i - 1; j >= 0 && cmp(tmp, array[j]) < 0; j--)
                        array[j + 1] = array[j];
                array[j + 1] = tmp;
        }
}
